home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / haeberli / libgutil / follow.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  11KB  |  534 lines
  1. /*
  2.  * Copyright 1991, 1992, 1993, 1994, Silicon Graphics, Inc.
  3.  * All Rights Reserved.
  4.  *
  5.  * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
  6.  * the contents of this file may not be disclosed to third parties, copied or
  7.  * duplicated in any form, in whole or in part, without the prior written
  8.  * permission of Silicon Graphics, Inc.
  9.  *
  10.  * RESTRICTED RIGHTS LEGEND:
  11.  * Use, duplication or disclosure by the Government is subject to restrictions
  12.  * as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
  13.  * and Computer Software clause at DFARS 252.227-7013, and/or in similar or
  14.  * successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
  15.  * rights reserved under the Copyright Laws of the United States.
  16.  */
  17. /*
  18.  *    follow -
  19.  *        Sweep a template along a curve. 
  20.  *
  21.  *                Paul Haeberli - 1990
  22.  */
  23. #include "stdio.h"
  24. #include "math.h"
  25. #include "vect.h"
  26. #include "sgiobj.h"
  27. #include "setjmp.h"
  28. #include "triangulate.h"
  29.  
  30. static newsegment();
  31. static normsegs();
  32. static getcornervect();
  33. static transtemp();
  34. static putobjvert();
  35.  
  36. float frand();
  37. sgiobj *follow();
  38. sgiobj *getfaces();
  39.  
  40. #define MAXPATH    1000
  41. #define MAXTEMP    1000
  42.  
  43. #define EPSILON    0.00001
  44.  
  45. typedef struct segment {
  46.     int prev, next;
  47.     vect p1, dp1, snorm1;
  48.     vect p2, dp2, snorm2;
  49.     vect gnorm;
  50. } segment;
  51.  
  52. static int ntemp, tempstart;
  53. static segment temp[MAXTEMP];
  54. static int npath, pathstart;
  55. static segment path[MAXPATH];
  56. static int trierror;
  57. static float noisemag;
  58.  
  59. /*
  60.  *    Describe the template
  61.  *
  62.  */
  63. tempbegin()
  64. {
  65.     ntemp = 0;
  66.     tempstart = 0;
  67. }
  68.  
  69. tempsegment(p1,dp1,p2,dp2)
  70. vect *p1,*dp1,*p2,*dp2;
  71. {
  72.     newsegment(temp,ntemp++,p1,dp1,p2,dp2);
  73.     if(ntemp == MAXTEMP) {
  74.     fprintf(stderr,"tempsegment: too many template segments\n");
  75.     exit(1);
  76.     }
  77. }
  78.  
  79. tempclose()
  80. {
  81.     if(tempstart != ntemp) {
  82.     if( (temp[tempstart].p1.x == temp[ntemp-1].p2.x) &&
  83.             (temp[tempstart].p1.y == temp[ntemp-1].p2.y) ) {
  84.         temp[tempstart].prev = ntemp-1;
  85.         temp[ntemp-1].next = tempstart;
  86.     } else {
  87.         temp[tempstart].prev = -1;
  88.         temp[ntemp-1].next = -1;
  89.     }
  90.     tempstart = ntemp;
  91.     }
  92. }
  93.  
  94. /*
  95.  *    Describe the path
  96.  *
  97.  */
  98. pathbegin()
  99. {
  100.     npath = 0;
  101.     pathstart = 0;
  102. }
  103.  
  104. pathsegment(p1,dp1,p2,dp2)
  105. vect *p1,*dp1,*p2,*dp2;
  106. {
  107.     newsegment(path,npath++,p1,dp1,p2,dp2);
  108.     if(npath == MAXPATH) {
  109.     fprintf(stderr,"pathsegment: too many path segments\n");
  110.     exit(1);
  111.     }
  112. }
  113.  
  114. pathclose()
  115. {
  116.     if(pathstart != npath) {
  117.     if( (path[pathstart].p1.x == path[npath-1].p2.x) &&
  118.             (path[pathstart].p1.y == path[npath-1].p2.y) ) {
  119.         path[pathstart].prev = npath-1;
  120.         path[npath-1].next = pathstart;
  121.     } else {
  122.         path[pathstart].prev = -1;
  123.         path[npath-1].next = -1;
  124.     }
  125.     pathstart = npath;
  126.     }
  127. }
  128.  
  129. pathnoise(mag)
  130. float mag;
  131. {
  132.     noisemag = mag;
  133. }
  134.  
  135. static float addnoise(v)
  136. float v;
  137. {
  138.     return v+noisemag*(frand()-0.5);
  139. }
  140.  
  141. static newsegment(seg,nseg,p1,dp1,p2,dp2)
  142. segment seg[];
  143. int nseg;
  144. vect *p1,*dp1,*p2,*dp2;
  145. {
  146.     vect slope;
  147.  
  148.     slope.x = p2->x-p1->x;
  149.     slope.y = p2->y-p1->y;
  150.     slope.z = 0.0;
  151.     seg[nseg].p1 = *p1;
  152.     seg[nseg].p1.z = 0.0;
  153.     seg[nseg].p2 = *p2;
  154.     seg[nseg].p2.z = 0.0;
  155.     if(dp1) {
  156.     seg[nseg].dp1 = *dp1;
  157.     seg[nseg].dp1.z = 0.0;
  158.     } else 
  159.     seg[nseg].dp1 = slope;
  160.     if(dp2) {
  161.     seg[nseg].dp2 = *dp2;
  162.     seg[nseg].dp2.z = 0.0;
  163.     } else 
  164.     seg[nseg].dp2 = slope;
  165.     seg[nseg].prev = nseg-1;
  166.     seg[nseg].next = nseg+1;
  167. }
  168.  
  169.  
  170. /*
  171.  *    Sweep the template along the path.
  172.  *
  173.  */
  174. sgiobj *follow()
  175. {
  176.     int looptemp, looppath;
  177.     int t, p; 
  178.     vect gvect1, gvect2;
  179.     vect svect1, svect2;
  180.     float x, y;
  181.     int nquads;
  182.     sgiobj *obj;
  183.     float *temp1, *temp2;
  184.     float *t1ptr, *t2ptr, *fptr;
  185.  
  186.     tempclose();
  187.     pathclose();
  188.     normsegs(temp,ntemp);
  189.     normsegs(path,npath);
  190.  
  191.     nquads = ntemp*npath;
  192.     obj = newtriobj(2*nquads);
  193.     fptr = (float*)obj->data;
  194.  
  195.     temp1 = (float*)mymalloc(2*ntemp*sizeof(float)*PNTLONGS);
  196.     temp2 = (float*)mymalloc(2*ntemp*sizeof(float)*PNTLONGS);
  197.  
  198.     for(p=0; p<npath; p++) {
  199.     getcornervect(&gvect1,path[p].prev,p);
  200.     getcornervect(&gvect2,p,path[p].next);
  201.  
  202.     transtemp(temp,temp1,&path[p].p1,&gvect1,&path[p].snorm1,ntemp);
  203.     transtemp(temp,temp2,&path[p].p2,&gvect2,&path[p].snorm2,ntemp);
  204.  
  205.     t1ptr = temp1;
  206.     t2ptr = temp2;
  207.     for(t=0; t<ntemp; t++) {
  208.  
  209.         bcopy(t1ptr+(0*PNTLONGS),fptr,PNTLONGS*sizeof(float));
  210.         fptr += PNTLONGS;
  211.         bcopy(t2ptr+(0*PNTLONGS),fptr,PNTLONGS*sizeof(float));
  212.         fptr += PNTLONGS;
  213.         bcopy(t1ptr+(1*PNTLONGS),fptr,PNTLONGS*sizeof(float));
  214.         fptr += PNTLONGS;
  215.  
  216.         bcopy(t2ptr+(1*PNTLONGS),fptr,PNTLONGS*sizeof(float));
  217.         fptr += PNTLONGS;
  218.         bcopy(t1ptr+(1*PNTLONGS),fptr,PNTLONGS*sizeof(float));
  219.         fptr += PNTLONGS;
  220.         bcopy(t2ptr+(0*PNTLONGS),fptr,PNTLONGS*sizeof(float));
  221.         fptr += PNTLONGS;
  222.  
  223.         t1ptr += 2*PNTLONGS;
  224.         t2ptr += 2*PNTLONGS;
  225.     }
  226.     }
  227.     free(temp1);
  228.     free(temp2);
  229.     return obj;
  230. }
  231.  
  232. static transtemp(temp,fptr,pos,gvect,gnorm,n)
  233. segment *temp;
  234. float *fptr;
  235. vect *pos, *gvect, *gnorm;
  236. int n;
  237. {
  238.     float x, y, z;
  239.     float nx, ny, nz;
  240.  
  241.     while(n--) {
  242.     x = pos->x+temp->p1.x*gvect->x;
  243.     y = pos->y+temp->p1.x*gvect->y;
  244.     z = temp->p1.y;
  245.     nx = temp->snorm1.x*gnorm->x;
  246.     ny = temp->snorm1.x*gnorm->y;
  247.     nz = temp->snorm1.y;
  248.     fptr[OFFSET_POINT+0] = x;
  249.     fptr[OFFSET_POINT+1] = y;
  250.     fptr[OFFSET_POINT+2] = z;
  251.     fptr[OFFSET_NORMAL+0] = nx;
  252.     fptr[OFFSET_NORMAL+1] = ny;
  253.     fptr[OFFSET_NORMAL+2] = nz;
  254.     fptr[OFFSET_UVS+0] = x;
  255.     fptr[OFFSET_UVS+1] = y;
  256.     fptr[OFFSET_UVS+2] = z;
  257.  
  258.     fptr += PNTLONGS;
  259.  
  260.     x = pos->x+temp->p2.x*gvect->x;
  261.     y = pos->y+temp->p2.x*gvect->y;
  262.     z = temp->p2.y;
  263.     nx = temp->snorm2.x*gnorm->x;
  264.     ny = temp->snorm2.x*gnorm->y;
  265.     nz = temp->snorm2.y;
  266.     fptr[OFFSET_POINT+0] = x;
  267.     fptr[OFFSET_POINT+1] = y;
  268.     fptr[OFFSET_POINT+2] = z;
  269.     fptr[OFFSET_NORMAL+0] = nx;
  270.     fptr[OFFSET_NORMAL+1] = ny;
  271.     fptr[OFFSET_NORMAL+2] = nz;
  272.     fptr[OFFSET_UVS+0] = x;
  273.     fptr[OFFSET_UVS+1] = y;
  274.     fptr[OFFSET_UVS+2] = z;
  275.  
  276.     fptr += PNTLONGS;
  277.  
  278.     temp++;
  279.     }
  280. }
  281.  
  282. static getcornervect(cvect,p1,p2)
  283. vect *cvect;
  284. int p1, p2;
  285. {
  286.     float dot;
  287.  
  288.     if(p1<0) {
  289.     *cvect = path[p2].gnorm;
  290.     } else if(p2<0) {
  291.     *cvect = path[p1].gnorm;
  292.     } else {
  293.     vadd(&path[p1].gnorm,&path[p2].gnorm,cvect);
  294.     dot = vdot(&path[p1].gnorm,cvect);
  295.     vscale(cvect,1.0/dot);
  296.     }
  297. }
  298.  
  299. static normsegs(segs,nsegs)
  300. segment *segs;
  301. int nsegs;
  302. {
  303.     int i;
  304.     float mag, dx, dy;
  305.  
  306.     if(segs == 0) {
  307.     fprintf(stderr,"follow: template or path has no segemets\n");
  308.     exit(1);
  309.     }
  310.     for(i=0; i<nsegs; i++) {
  311.     mag = sqrt(segs->dp1.x*segs->dp1.x + segs->dp1.y*segs->dp1.y);
  312.     if(mag<EPSILON) {
  313.         fprintf(stderr,"follow: bad poop 1\n");
  314.         exit(1);
  315.     }
  316.     segs->snorm1.x = segs->dp1.y/mag;
  317.     segs->snorm1.y = -segs->dp1.x/mag;
  318.  
  319.     mag = sqrt(segs->dp2.x*segs->dp2.x + segs->dp2.y*segs->dp2.y);
  320.     if(mag<EPSILON) {
  321.         fprintf(stderr,"follow: bad poop 2\n");
  322.         exit(1);
  323.     }
  324.     segs->snorm2.x = segs->dp2.y/mag;
  325.     segs->snorm2.y = -segs->dp2.x/mag;
  326.  
  327.     dx = segs->p2.x - segs->p1.x;
  328.     dy = segs->p2.y - segs->p1.y;
  329.     mag = sqrt(dx*dx+dy*dy);
  330.     if(mag<EPSILON) {
  331.         fprintf(stderr,"follow: bad poop %d %f %f 3\n",i,dx,dy);
  332.         exit(1);
  333.     }
  334.     segs->gnorm.x = dy/mag;
  335.     segs->gnorm.y = -dx/mag;
  336.     segs->gnorm.z = 0.0;
  337.     segs++;
  338.     }
  339. }
  340.  
  341. static float *objfptr;
  342. static sgiobj *faceobj;
  343. static int polyp, outtri, maxtri;
  344. static float facesign, facez;
  345.  
  346. /* 
  347.  *     triangulation stuff follows
  348.  *
  349.  */
  350. static int trifunc(verts)
  351. float *verts[3];
  352. {
  353.     float x, y, z;
  354.     int i, offset;
  355.     float *fptr;
  356.  
  357.     for(i=0; i<3; i++) {
  358.     fptr = verts[i];
  359.     x = fptr[0];
  360.     y = fptr[1];
  361.     z = facez;
  362.     if(facesign>0.0) 
  363.         offset = i;
  364.     else
  365.         offset = 2-i;
  366.     putobjvert(objfptr+offset*PNTLONGS,x,y,z);
  367.     }
  368.     objfptr += 3*PNTLONGS;
  369.     outtri++;
  370. }
  371.  
  372. static putobjvert(fptr,x,y,z)
  373. float *fptr;
  374. float x, y, z;
  375. {
  376.     fptr[OFFSET_NORMAL+0] = 0.0;
  377.     fptr[OFFSET_NORMAL+1] = 0.0;
  378.     fptr[OFFSET_NORMAL+2] = facesign;
  379.     fptr[OFFSET_POINT+0] = x;
  380.     fptr[OFFSET_POINT+1] = y;
  381.     fptr[OFFSET_POINT+2] = z;
  382.     fptr[OFFSET_UVS+0] = x;
  383.     fptr[OFFSET_UVS+1] = y;
  384.     fptr[OFFSET_UVS+2] = z;
  385. }
  386.  
  387. static void out_bgnpoly()
  388. {
  389.     mesh_callback(trifunc);
  390. }
  391.  
  392. static void out_endpoly()
  393. {
  394. }
  395.  
  396. static void out_bgntmesh()
  397. {
  398.     mesh_bgntmesh();
  399. }
  400.  
  401. static void out_swaptmesh()
  402. {
  403.     mesh_swaptmesh();
  404. }
  405.  
  406. static void out_vertex(iptr)
  407. int *iptr;
  408. {
  409.     mesh_vert(iptr);
  410. }
  411.  
  412. static void out_endtmesh()
  413. {
  414.     mesh_endtmesh();
  415. }
  416.  
  417. static void out_error(str)
  418. char *str;
  419. {
  420.     fprintf(stderr,"triangulate error [%s]\n",str);
  421.     trierror = 1;
  422. }
  423.  
  424. /*
  425.  *    face support follows
  426.  *
  427.  */
  428. sgiobj *getfaces()
  429. {
  430.     int nlevels; 
  431.     int ntri, tottri;
  432.     int p, t, added;
  433.     int nverts;
  434.     float x, y;
  435.     TriangulatorObj *tripak;
  436.  
  437.     tempclose();
  438.     pathclose();
  439.     normsegs(temp,ntemp);
  440.     normsegs(path,npath);
  441.  
  442. /* count levels */
  443.     nlevels = 0;
  444.     for(t=0; t<ntemp; t++) {
  445.     if(temp[t].p1.x == 0.0 || temp[t].p2.x == 0.0) 
  446.         nlevels++;
  447.     }
  448.  
  449. /* count number of ring segments */
  450.     nverts = 0;
  451.     p = 0;
  452.     while(1) {
  453.     while(p<npath) {
  454.         if(path[p].prev>p) {
  455.         break;
  456.         }
  457.         p++;
  458.     }
  459.     if(p == npath) 
  460.         break;
  461.     while(path[p].next>p) {
  462.         nverts+=2;    /* worst case */
  463.         p++;
  464.     }
  465.     p++;
  466.     nverts++;
  467.     }
  468.  
  469.     ntri = nverts;
  470.     tottri = ntri*nlevels;
  471.     maxtri = tottri;
  472.     if(tottri==0)
  473.     return 0;
  474.     faceobj = newtriobj(tottri);
  475.     objfptr = (float *)faceobj->data;
  476.     outtri = 0;
  477.     added = 0;
  478.     trierror = 0;
  479.     tripak = newTriangulator(out_bgnpoly,out_endpoly,
  480.      out_bgntmesh,out_swaptmesh,out_vertex,out_endtmesh,out_error);
  481.     for(t=0; t<ntemp; t++) {
  482.     if(temp[t].p1.x == 0.0 || temp[t].p2.x == 0.0) {
  483.         if(temp[t].p1.x == 0.0) {
  484.         facez = temp[t].p1.y;
  485.         facesign = -1.0;
  486.         } else {
  487.         facez = temp[t].p2.y;
  488.         facesign = 1.0;
  489.         }
  490.         p = 0;
  491.         in_bgnpoly(tripak,0);
  492.         while(1) {
  493.         while(p<npath) {
  494.             if(path[p].prev>p)
  495.             break;
  496.             p++;
  497.         }
  498.         if(p >= npath) 
  499.             break;
  500.         in_bgnloop(tripak,TRI_UNKNOWN);
  501.         while(path[p].next>p) {
  502.             x = path[p].p1.x;
  503.             y = path[p].p1.y;
  504.             if(noisemag>0.0)
  505.             in_vertex(tripak,addnoise(x),addnoise(y),(int *)(&path[p].p1));
  506.             else
  507.             in_vertex(tripak,addnoise(x),addnoise(y),(int *)(&path[p].p1));
  508.             p++;
  509.             added++;
  510.         }
  511.         x = path[p].p1.x;
  512.         y = path[p].p1.y;
  513.         if(noisemag>0.0)
  514.             in_vertex(tripak,addnoise(x),addnoise(y),(int *)(&path[p].p1));
  515.         else
  516.             in_vertex(tripak,x,y,(int *)(&path[p].p1));
  517.         p++;
  518.         added++;
  519.         in_endloop(tripak);
  520.         }
  521.         in_endpoly(tripak);
  522.     }
  523.     }
  524.     freeTriangulator(tripak);
  525.     if(trierror)
  526.     return 0;
  527.     if(outtri>tottri) {
  528.     fprintf(stderr,"get face bad poop %d %d\n",outtri,tottri);
  529.     }
  530.     faceobj->nlongs = outtri*3*PNTLONGS;
  531.     return faceobj;
  532. }
  533.  
  534.